
class LRUCache{
private:
	list<pair<int,int>> cache;
	unordered_map<int,List<pair<int,int>>::iterator> key2node;
	int cap;
	public LRUCache(int capacity):cap(capacity){}
	int get(int key){
		if(key2node.find(key)==key2node.end()){
			return -1;
		}
		pair<int,int> node = *key2node[key];
		cache.erase(key2node[key]);// rease 只能删除迭代器
		cache.push_front(node);
		return node.seccond;
	}
	void put(int key,int val){
		auto newNode = make_pair(key,value);
		if(key2node.cout(key)){
			cache.erase(key2node[key]);
		}
		else{
			if(cap==cache.size()){
				key2node.erase(cache.back().first);
				cache.pop_back();
			}
		}
		cache.push_front(newNode);
		key2node[key]=cache.begin();
	}
}